// 6.2.2 单词基因变化 -> LC127

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
#include <string>
using namespace std;

// 返回两个单词是否基因变化（即刚好只有一个字母不同）
bool isGeneChange(const string& s1, const string& s2) {
    int n = s1.length(), d = 0;
    for (int i = 0; i < n; i++) {
        if (s1[i] != s2[i]) {
            d++;
            if (d > 1)
                return false;
        }
    }
    return d == 1;
}

// 计算单词基因转换序列的长度
int wordGeneLength(const string& beginWord, const string& endWord, const vector<string>& wordList) {
    // 用字典表保存每个单词的最小演变次数
    unordered_map<string, int> steps;
    steps[beginWord] = 0;
    for (const auto& s : wordList)
        steps[s] = -1;

    // 创建队列，保存状态为当前搜索的单词
    queue<string> queue;
    queue.push(beginWord);

    // BFS - 基于队列开始搜索
    while (!queue.empty()) {
        // 取出当前单词，记为s
        string s = queue.front();
        queue.pop();
        // 从字典表取出当前长度，记为p
        int p = steps[s];
        // 搜索下一个可以演变的单词
        for (const auto& t : wordList) {
            // 1. 判断是否新的目标点
            if (steps[t] == -1 && isGeneChange(s, t)) {
                // 2. 判断是否已到达终点，是则直接返回
                if (t == endWord)
                    return p + 1;
                // 3. 计算保存目标点状态
                steps[t] = p + 1;
                // 4. 将目标点状态放入队列尾部
                queue.push(t);
            }
        }
    }

    // 没有结果返回-1
    return -1;
}

int main() {
    string beginWord = "hit", endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog", "log", "cog"};
    int ans = wordGeneLength(beginWord, endWord, wordList);
    cout << "单词基因转换次数为: " << ans << endl;
    return 0;
}